Address lookup is one of the fundamental functions of a router, along with buffering, scheduling and switching of packets. The address lookup aspect is a particularly critical function for the building-routers that need to support multi-Gb/s links. The increasing traffic demand in the present internet scenario requires at least three key factors to keep pace if the Internet is to continue to provide good services: link speed, router data throughput, and packet forwarding rates. Readily available solutions exist for the first two factors. For example, fiber-optic cables can provide faster links, and switching technology can be used to move packets from the input interface of a router to the corresponding output interface at gigabit speed. There is still need for innovation with address look up and with the third factor, i.e., packet forwarding.
The major step in packet forwarding is to lookup the destination address (of an incoming packet) in the routing database. While there are other chores such as updating TTL (Tagging, Tracking, and Locating) fields, these chores are computationally inexpensive compared to the major task of address lookup. Bridges only do exact matching on the destination MAC (Media Access Control) address, while internet routers have to search their database for the longest prefix matching a destination IP (Internet Protocol) address. Thus, standard matching techniques for exact matching, such as perfect hashing, binary search, and standard Content Addressable Memories (CAMs) cannot be used for internet address lookups.
It is noted that prefix matching was introduced in the early 1990s, when Classless Inter-Domain Routing (CIDR) was deployed to allow for arbitrary aggregation of networks to reduce routing table entries. This means in principle that the prefixes are compared bit by bit to the given address and that the routing information associated with the longest of the matching prefixes should be used to forward the packet.
An IPv4 routing table comprises a set of routers, which is updated by routing protocols such as RIP (Routing Information Protocol) or OSPF (Open Shortest Path first), wherein each route determines the outgoing interface for a set of IP destination addresses, which is represented by an IP address and a subnet mask. Thus, presently an IP router's database consists of a number of address prefixes. IP routers do a routing lookup in a routing table to determine where IP datagrams are to be forwarded. The result of the operation is the next hop on the path to-wards the destination. An entry in a routing table is conceptually an arbitrary length prefix with associated next-hop information. Routing lookup must find the routing entry with the longest matching prefix. When an IP router receives a packet, it must compute which of the prefixes in its database has the longest match when compared to the destination address in the packet. The packet is then forwarded to the output link associated with that prefix. For example, a forwarding database may have the prefixes P1=0101, P2=0101101, and P3=010110101011. An address whose first 12 bits are 010101101011 has a longest matching prefix P1. On the other hand, an address whose first 12 bits are 010110101101 has the longest matching prefix P3.
The use of longest matching prefix in forwarding has allowed IP routers to accommodate various levels of address hierarchies, and has allowed different parts of the network to have different views of the address hierarchy. The issue regarding longest prefix matching merits review and innovation.